Andreas Kirsch
Aufgabe 2 "Robot Dressing"

1. Lsungsidee:
===============

Man kann die Angaben zur Reihenfolge leicht als Bedinungen der Art A => B sehen erkennen. Man also fr jedes Kleidungsstck (allgemeiner kann man es als Item bezeichnen) eine Menge von Items finden, die vorausgesetzt sind. Wenn die Menge leer ist, so kann das Item egal wann angezogen werden, da es ja anderen vorausgesetzt sind.
Um nun eine mgliche Ankleidungsreihenfolge zu bestimmen kann man folgenden, rekursicven Algorithmus benutzen:

Eingaben: Menge A aller schon angezogenen Items, Menge V aller noch verbliebenen Items
Am Anfang ist A leer und V enthlt alle Items.

1) Fine ein Item v der Menge V, fr dessen Menge R der vorausgesetzten Items gilt:
 R \ A = {}, dann kann das Item angezogen werden. Wird kein einziges gefunden, springe zu Schritt 3.
2) Sei A' = A U {v} (U steht fr 'vereinigt mit') und V' = V \ {v}, dann soll der Algorithmus mit A' und V' (statt A und V) von vorne ausgefhrt werden.
3) Entweder ist die Menge V leer und alle Items wurden angezogen und unser Algorithmus war erfolgreich, oder V ist nicht leer und es gibt Items, die nicht angezogen werden knnen, und es gibt keine Lsung fr das Problem.

Die Reihenfolge ergibt sich aus der Reihenfolge mit der Items in A eingefgt werden. Um alle Lsungen zu finden, kann man Teillisten verwenden, die bei jeder weitergegeben werden. Wenn V dann leer ist, wird diese Liste dann zur Menge der Lsungen hinzugefgt und der Algorithmus macht mit den vorherigen A und V weiter, sucht also das nchste Item v, fr welches die Bedingung aus 1) gilt, etc etc. 
Man kann sich das ganze als rekursives Durchqueren eines Baumes vorstellen, wobei der Pfad gespeichert wird und die Lsungsreihenfolge darstellt.

2. Programm-Dokumentation:
==========================

Zuerst einmal mchte ich das Eingabeformat beschreiben. Eine einfache Eingabedatei kann z.B so aussehen:

[Items]
A
B 
C

[Rules]
A B
A C

#EOF

Nach [items] folgt eine Auflistung aller gltigen Items und nach [rules] folgen die Regeln, wobei z.b. A B bedeutet A vor B bzw A => B.

Der Dateiname der Eingabedatei wird als erste Befehlszeilenparameter bergeben.
Als zweiter Befehlszeilenparameter kann auch noch die Option single angegeben werden, was das Progamm veranlasst nur eine einzige Lsung auszugeben.
Dabei wird der gleiche Algorithmus verwendet wie bei der Bestimmung aller Lsungen - es werden also auch alle Lsungen bestimmt. Der Grund dafr liegt darin, da die Bestimmung aller Lsungen nur einiger kurzer Ergnzungen des Grundalgorithmus bedarf und ich nicht den Quellcode durch zwei gleiche Algorithmen unntig aufblhen wollte.

Zur Entwicklung und zur Umsetzung der Lsungsidee:
Ich verwende extensiv STL, benutze als typedefs und andere Konstrukte, die den Quellcode meiner Meinung nach nicht besonders schn aussehen lassen, ihn aber dafr nur auf das wichtigste beschrnken.
Es gibt 2 wichtige Methoden: Item::CanBeInserted( const ConstPointerSet &usedItems ) und DressingSolutions::Solve_r( Item::ConstPointerSet &usedItems, ItemOrder &currentOrder ).
Die Datentypen sind der Lsungsidee entsprechend nachmodelliert:
Item enthlt die Eigenschaften eines Items/Kleidungsstckes: die Menge aller anderen vorausgesetzten Items und den Namen des Items. ItemOrder speichert eine Reihenfolge, und DressingSolutions speichert alle Lsungsreihenfolgen.

Nun zu den beiden wichtigen Methoden:
Item::CanBeInserted( const ConstPointerSet &usedItems ) berprft nichts weiter als die Bedingung in Schritt 1) des Algorithmuses: Die Methode liefert "wahr" zurck, falls die Menge der vorausgesetzten Items des Item R *ohne* die Menge der bereits angezogenen Items A gleich der leeren Menge ist, also falls alle vorausgesetzten Items angezogen sind.
Um dies zu prfen, wird folgender Algorithmus verwendet:
A und R sind aufsteigend nach einem eindeutigen Kriterium sortiert (z.B. beide Beziehen sich auf die gleiche Gesamtmenge von Items im Speicher durch Zeiger und die Adresse der Datenstrukturen wre dann ein solches Kriterium).
1. Wiederhole bis entweder A oder R vom Anfang an vollstndig durchlaufen ist:
	1) Seien a und r, die derzeitig ausgewhlten Elemente der Mengen A bzw R.
	2) Falls r < a, so gibt es ein Element aus R, dass nicht in A vorkommt und die Prfung
		ist beendet, da R \ A nicht leer ist und CanBeInserted gibt gleich "falsch" zurck.
	3) Falls a < r, so wird zum nchsten Element von A iteriert und wieder von 1. angefangen
	4) Falls a = r, dann wird zum nchsten Element von A unr R weiter iteriert und es wird
		wieder bei 1. angefangen
2. Falls vollstndig durch R iteriert wurde, dann war die Prfung erfolgreich, da alle Elemente von R durchlaufen wurden und auch jedes Element in A vorkam (,da sonst die Prfung vorzeitig beendet worden wre).
3. Falls nicht vollstndig durch R iteriert wurde, so muss die Schleife beendet worden sein, weil vollstndig durch A iteriert wurde, und R enthlt damit Elemente die nicht in A sein knnen, da sie grer als das grte Element in A sind und folglich in der aufsteigend sortierten Menge A nicht enthalten sind, und die Prfung ist damit negativ ausgefallen.

DressingSolutions::Solve_r( Item::ConstPointerSet &usedItems, ItemOrder &currentOrder ) ist eigentlich eine recht genaue Implementierung des Algorithmus, es gibt jedoch zwei nderungen, die aber nicht das uere Verhalten an sich betreffen:
1. Es wird am Anfang der Funktion berprft, ob schon alle Kleidungsstcke angezogen wurden und
2. die Menge V der verbliebenen Items wird implizit durch die Menge aller Items ohne die Menge der angezogenen Items dargestell, deshalb wird durch die Menge aller Items iteriert statt durch V und neben der Bedingung des Algorithmuses wird auch noch berprft, ob ein Item nicht schon Element der angezogenen Items ist. Dadurch wird sichergestellt, dass auch wirklich nur Elemente, die die Menge V ausmachen wrden, getestet werden.

3. Programm-Ablaufprotokoll
===========================

[...]>"Aufgabe 2.exe" test1.txt 
90 Lsungen gefunden

Lsung #1: Bluse->Mtze->Strmpfe->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #2: Bluse->Mtze->Strmpfe->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #3: Bluse->Mtze->Strmpfe->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #4: Bluse->Mtze->Strmpfe->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #5: Bluse->Mtze->Strmpfe->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #6: Bluse->Strmpfe->Hose->Mtze->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #7: Bluse->Strmpfe->Hose->Mtze->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #8: Bluse->Strmpfe->Hose->Mtze->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #9: Bluse->Strmpfe->Hose->Mtze->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #10: Bluse->Strmpfe->Hose->Mtze->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #11: Bluse->Strmpfe->Hose->Pullover->Mtze->Schal->Jacke->Handschuhe->Schuhe
Lsung #12: Bluse->Strmpfe->Hose->Pullover->Mtze->Schal->Jacke->Schuhe->Handschuhe
Lsung #13: Bluse->Strmpfe->Hose->Pullover->Mtze->Schal->Schuhe->Jacke->Handschuhe
Lsung #14: Bluse->Strmpfe->Hose->Pullover->Mtze->Schuhe->Schal->Jacke->Handschuhe
Lsung #15: Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Handschuhe->Mtze->Schuhe
Lsung #16: Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe->Mtze
Lsung #17: Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Mtze->Handschuhe->Schuhe
Lsung #18: Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Mtze->Schuhe->Handschuhe
Lsung #19: Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe->Mtze
Lsung #20: Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Schuhe->Mtze->Handschuhe
Lsung #21: Bluse->Strmpfe->Hose->Pullover->Schal->Mtze->Jacke->Handschuhe->Schuhe
Lsung #22: Bluse->Strmpfe->Hose->Pullover->Schal->Mtze->Jacke->Schuhe->Handschuhe
Lsung #23: Bluse->Strmpfe->Hose->Pullover->Schal->Mtze->Schuhe->Jacke->Handschuhe
Lsung #24: Bluse->Strmpfe->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe->Mtze
Lsung #25: Bluse->Strmpfe->Hose->Pullover->Schal->Schuhe->Jacke->Mtze->Handschuhe
Lsung #26: Bluse->Strmpfe->Hose->Pullover->Schal->Schuhe->Mtze->Jacke->Handschuhe
Lsung #27: Bluse->Strmpfe->Hose->Pullover->Schuhe->Mtze->Schal->Jacke->Handschuhe
Lsung #28: Bluse->Strmpfe->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe->Mtze
Lsung #29: Bluse->Strmpfe->Hose->Pullover->Schuhe->Schal->Jacke->Mtze->Handschuhe
Lsung #30: Bluse->Strmpfe->Hose->Pullover->Schuhe->Schal->Mtze->Jacke->Handschuhe
Lsung #31: Bluse->Strmpfe->Hose->Schuhe->Mtze->Pullover->Schal->Jacke->Handschuhe
Lsung #32: Bluse->Strmpfe->Hose->Schuhe->Pullover->Mtze->Schal->Jacke->Handschuhe
Lsung #33: Bluse->Strmpfe->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe->Mtze
Lsung #34: Bluse->Strmpfe->Hose->Schuhe->Pullover->Schal->Jacke->Mtze->Handschuhe
Lsung #35: Bluse->Strmpfe->Hose->Schuhe->Pullover->Schal->Mtze->Jacke->Handschuhe
Lsung #36: Bluse->Strmpfe->Mtze->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #37: Bluse->Strmpfe->Mtze->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #38: Bluse->Strmpfe->Mtze->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #39: Bluse->Strmpfe->Mtze->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #40: Bluse->Strmpfe->Mtze->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #41: Mtze->Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #42: Mtze->Bluse->Strmpfe->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #43: Mtze->Bluse->Strmpfe->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #44: Mtze->Bluse->Strmpfe->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #45: Mtze->Bluse->Strmpfe->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #46: Mtze->Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #47: Mtze->Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #48: Mtze->Strmpfe->Bluse->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #49: Mtze->Strmpfe->Bluse->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #50: Mtze->Strmpfe->Bluse->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #51: Strmpfe->Bluse->Hose->Mtze->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #52: Strmpfe->Bluse->Hose->Mtze->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #53: Strmpfe->Bluse->Hose->Mtze->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #54: Strmpfe->Bluse->Hose->Mtze->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #55: Strmpfe->Bluse->Hose->Mtze->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #56: Strmpfe->Bluse->Hose->Pullover->Mtze->Schal->Jacke->Handschuhe->Schuhe
Lsung #57: Strmpfe->Bluse->Hose->Pullover->Mtze->Schal->Jacke->Schuhe->Handschuhe
Lsung #58: Strmpfe->Bluse->Hose->Pullover->Mtze->Schal->Schuhe->Jacke->Handschuhe
Lsung #59: Strmpfe->Bluse->Hose->Pullover->Mtze->Schuhe->Schal->Jacke->Handschuhe
Lsung #60: Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Handschuhe->Mtze->Schuhe
Lsung #61: Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe->Mtze
Lsung #62: Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Mtze->Handschuhe->Schuhe
Lsung #63: Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Mtze->Schuhe->Handschuhe
Lsung #64: Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe->Mtze
Lsung #65: Strmpfe->Bluse->Hose->Pullover->Schal->Jacke->Schuhe->Mtze->Handschuhe
Lsung #66: Strmpfe->Bluse->Hose->Pullover->Schal->Mtze->Jacke->Handschuhe->Schuhe
Lsung #67: Strmpfe->Bluse->Hose->Pullover->Schal->Mtze->Jacke->Schuhe->Handschuhe
Lsung #68: Strmpfe->Bluse->Hose->Pullover->Schal->Mtze->Schuhe->Jacke->Handschuhe
Lsung #69: Strmpfe->Bluse->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe->Mtze
Lsung #70: Strmpfe->Bluse->Hose->Pullover->Schal->Schuhe->Jacke->Mtze->Handschuhe
Lsung #71: Strmpfe->Bluse->Hose->Pullover->Schal->Schuhe->Mtze->Jacke->Handschuhe
Lsung #72: Strmpfe->Bluse->Hose->Pullover->Schuhe->Mtze->Schal->Jacke->Handschuhe
Lsung #73: Strmpfe->Bluse->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe->Mtze
Lsung #74: Strmpfe->Bluse->Hose->Pullover->Schuhe->Schal->Jacke->Mtze->Handschuhe
Lsung #75: Strmpfe->Bluse->Hose->Pullover->Schuhe->Schal->Mtze->Jacke->Handschuhe
Lsung #76: Strmpfe->Bluse->Hose->Schuhe->Mtze->Pullover->Schal->Jacke->Handschuhe
Lsung #77: Strmpfe->Bluse->Hose->Schuhe->Pullover->Mtze->Schal->Jacke->Handschuhe
Lsung #78: Strmpfe->Bluse->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe->Mtze
Lsung #79: Strmpfe->Bluse->Hose->Schuhe->Pullover->Schal->Jacke->Mtze->Handschuhe
Lsung #80: Strmpfe->Bluse->Hose->Schuhe->Pullover->Schal->Mtze->Jacke->Handschuhe
Lsung #81: Strmpfe->Bluse->Mtze->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #82: Strmpfe->Bluse->Mtze->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #83: Strmpfe->Bluse->Mtze->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #84: Strmpfe->Bluse->Mtze->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #85: Strmpfe->Bluse->Mtze->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe
Lsung #86: Strmpfe->Mtze->Bluse->Hose->Pullover->Schal->Jacke->Handschuhe->Schuhe
Lsung #87: Strmpfe->Mtze->Bluse->Hose->Pullover->Schal->Jacke->Schuhe->Handschuhe
Lsung #88: Strmpfe->Mtze->Bluse->Hose->Pullover->Schal->Schuhe->Jacke->Handschuhe
Lsung #89: Strmpfe->Mtze->Bluse->Hose->Pullover->Schuhe->Schal->Jacke->Handschuhe
Lsung #90: Strmpfe->Mtze->Bluse->Hose->Schuhe->Pullover->Schal->Jacke->Handschuhe

[...]>"Aufgabe 2.exe" test3.txt
24 Lsungen gefunden

Lsung #1: Halskette->Socken->Boxershort->Tshirt->Hose->Pullover->Jacke->Schuhe
Lsung #2: Halskette->Socken->Boxershort->Tshirt->Pullover->Hose->Jacke->Schuhe
Lsung #3: Halskette->Socken->Boxershort->Tshirt->Pullover->Jacke->Hose->Schuhe
Lsung #4: Socken->Boxershort->Halskette->Tshirt->Hose->Pullover->Jacke->Schuhe
Lsung #5: Socken->Boxershort->Halskette->Tshirt->Pullover->Hose->Jacke->Schuhe
Lsung #6: Socken->Boxershort->Halskette->Tshirt->Pullover->Jacke->Hose->Schuhe
Lsung #7: Socken->Boxershort->Tshirt->Halskette->Hose->Pullover->Jacke->Schuhe
Lsung #8: Socken->Boxershort->Tshirt->Halskette->Pullover->Hose->Jacke->Schuhe
Lsung #9: Socken->Boxershort->Tshirt->Halskette->Pullover->Jacke->Hose->Schuhe
Lsung #10: Socken->Boxershort->Tshirt->Hose->Halskette->Pullover->Jacke->Schuhe
Lsung #11: Socken->Boxershort->Tshirt->Hose->Pullover->Halskette->Jacke->Schuhe
Lsung #12: Socken->Boxershort->Tshirt->Hose->Pullover->Jacke->Halskette->Schuhe
Lsung #13: Socken->Boxershort->Tshirt->Hose->Pullover->Jacke->Schuhe->Halskette
Lsung #14: Socken->Boxershort->Tshirt->Pullover->Halskette->Hose->Jacke->Schuhe
Lsung #15: Socken->Boxershort->Tshirt->Pullover->Halskette->Jacke->Hose->Schuhe
Lsung #16: Socken->Boxershort->Tshirt->Pullover->Hose->Halskette->Jacke->Schuhe
Lsung #17: Socken->Boxershort->Tshirt->Pullover->Hose->Jacke->Halskette->Schuhe
Lsung #18: Socken->Boxershort->Tshirt->Pullover->Hose->Jacke->Schuhe->Halskette
Lsung #19: Socken->Boxershort->Tshirt->Pullover->Jacke->Halskette->Hose->Schuhe
Lsung #20: Socken->Boxershort->Tshirt->Pullover->Jacke->Hose->Halskette->Schuhe
Lsung #21: Socken->Boxershort->Tshirt->Pullover->Jacke->Hose->Schuhe->Halskette
Lsung #22: Socken->Halskette->Boxershort->Tshirt->Hose->Pullover->Jacke->Schuhe
Lsung #23: Socken->Halskette->Boxershort->Tshirt->Pullover->Hose->Jacke->Schuhe
Lsung #24: Socken->Halskette->Boxershort->Tshirt->Pullover->Jacke->Hose->Schuhe

[...]>"Aufgabe 2.exe" test3.txt
7 Lsungen gefunden

Lsung #1: Socken->Unterhose->Unterhemd->Strumpfhose->Schneeanzug->Mtze->Schneebrille->Wintersocken->Schuhe->Schneeeisen
Lsung #2: Socken->Unterhose->Unterhemd->Strumpfhose->Schneeanzug->Mtze->Wintersocken->Schneebrille->Schuhe->Schneeeisen
Lsung #3: Socken->Unterhose->Unterhemd->Strumpfhose->Schneeanzug->Wintersocken->Mtze->Schneebrille->Schuhe->Schneeeisen
Lsung #4: Socken->Unterhose->Unterhemd->Strumpfhose->Wintersocken->Schneeanzug->Mtze->Schneebrille->Schuhe->Schneeeisen
Lsung #5: Socken->Unterhose->Unterhemd->Wintersocken->Strumpfhose->Schneeanzug->Mtze->Schneebrille->Schuhe->Schneeeisen
Lsung #6: Socken->Unterhose->Wintersocken->Unterhemd->Strumpfhose->Schneeanzug->Mtze->Schneebrille->Schuhe->Schneeeisen
Lsung #7: Socken->Wintersocken->Unterhose->Unterhemd->Strumpfhose->Schneeanzug->Mtze->Schneebrille->Schuhe->Schneeeisen